0% completed
Problem Statement
serialization means converting a data structure or object into a sequence of bits that can be stored or sent over a network. Deserialization is the reverse process, which takes this sequence and recreates the original object or data structure.
Design an algorithm to serialize and deserialize a binary search tree (BST).
The serialization should convert the BST into a string, and deserialization should reconstruct the original BST from this string. There is no restriction on how your serialization/deserialization algorithm should work.
Examples
Example 1:
- Input: root = [4, 2, 6, 1, 3, null, 7]
- Expected Output: [4, 2, 6, 1, 3, null, 7]
- Justification: The output is the same as the input.
Example 2:
- Input: root = [8, 5, 10, 2, null, null, 12]
- Expected Output: [8, 5, 10, 2, null, null, 12]
- Justification: The output is the same as the input.
Example 3:
- Input: root = [15, 10, null, 5, 12, null, null, null, 13]
- Expected Output: [15, 10, null, 5, 12, null, null, null, 13]
- Justification: The output is the same as the input.
Constraints:
- The number of nodes in the tree is in the range [0, 104].
- 0 <= Node.val <= 104
- The input tree is guaranteed to be a binary search tree.
Solution
To solve this problem, we will use a pre-order traversal approach to serialize the binary search tree (BST). Pre-order traversal is chosen because it processes the current node before its children, which allows the serialized string to capture the hierarchy of the BST effectively. During serialization, we will append each node's value to a string and use a special symbol like "#" to denote null nodes. This approach ensures that every position of a node or a null is represented in the serialized format, making it easier to recreate the tree during deserialization.
For deserialization, we will read the serialized string and use a queue to maintain the order of elements. Starting from the root, we will construct the tree recursively by assigning left and right children based on the serialized string. This approach is effective as it allows us to restore the original tree structure while maintaining a compact serialized format.
Step-by-Step Algorithm
Serialization Process:
-
Initialize a StringBuilder:
- Create a
StringBuilderobject to store the serialized result. This will efficiently handle string concatenations.
- Create a
-
Perform Pre-order Traversal:
- Call a helper function
serializeHelperwith the root node and theStringBuilderas arguments.
- Call a helper function
-
Helper Function (serializeHelper):
- Check if the Current Node is Null:
- If the current node is
null, append"#,"to theStringBuilder. This symbol#represents a null or missing child. - Return immediately since there are no further nodes to traverse.
- If the current node is
- Process the Current Node:
- Append the value of the current node followed by a comma
","to theStringBuilder.
- Append the value of the current node followed by a comma
- Recur for the Left Subtree and Right Subtree:
- Call
serializeHelperrecursively with the left child of the current node. - Call
serializeHelperrecursively with the right child of the current node.
- Call
- Check if the Current Node is Null:
-
Return the Serialized String:
- Convert the
StringBuilderto a string usingtoString()method. - This string represents the serialized form of the BST.
- Convert the
Deserialization Process:
-
Split the Serialized String:
- Split the serialized string by commas
","to get an array of node values. - Convert this array into a
Queueto maintain the order of nodes to be processed.
- Split the serialized string by commas
-
Reconstruct the Tree:
- Call a helper function
deserializeHelperwith the queue of node values.
- Call a helper function
-
Helper Function (deserializeHelper):
- Get the Next Node Value:
- Retrieve the next node value from the queue using
poll().
- Retrieve the next node value from the queue using
- Check for Null Node:
- If the retrieved value is
"#", returnnullbecause this represents a null child.
- If the retrieved value is
- Create a New TreeNode:
- Convert the node value to an integer and create a new
TreeNode.
- Convert the node value to an integer and create a new
- Recur for the Left Subtree:
- Call
deserializeHelperrecursively to construct the left child. - Assign the result to the left child of the current node.
- Call
- Recur for the Right Subtree:
- Call
deserializeHelperrecursively to construct the right child. - Assign the result to the right child of the current node.
- Call
- Return the Reconstructed Node:
- Return the current node after both left and right children are constructed.
- Get the Next Node Value:
-
Return the Root of the Reconstructed Tree:
- The root returned by
deserializeHelperrepresents the reconstructed tree.
- The root returned by
Algorithm Walkthrough
Input: root = [4, 2, 6, 1, 3, null, 7]
Serialization Walkthrough:
-
Start with Root Node:
- Initialize
StringBuilder sb = "". - Call
serializeHelper(root = 4, sb).
- Initialize
-
Processing Node 4:
- Append "4," to
sb→sb = "4,". - Recur for left subtree: Call
serializeHelper(root.left = 2, sb).
- Append "4," to
-
Processing Node 2:
- Append "2," to
sb→sb = "4,2,". - Recur for left subtree: Call
serializeHelper(root.left = 1, sb).
- Append "2," to
-
Processing Node 1:
- Append "1," to
sb→sb = "4,2,1,". - Recur for left child: Node is
null, append "#," →sb = "4,2,1,#,". - Recur for right child: Node is
null, append "#," →sb = "4,2,1,#,#,".
- Append "1," to
-
Back to Node 2:
- Recur for right subtree: Call
serializeHelper(root.right = 3, sb).
- Recur for right subtree: Call
-
Processing Node 3:
- Append "3," to
sb→sb = "4,2,1,#,#,3,". - Recur for left child: Node is
null, append "#," →sb = "4,2,1,#,#,3,#,". - Recur for right child: Node is
null, append "#," →sb = "4,2,1,#,#,3,#,#,".
- Append "3," to
-
Back to Node 4:
- Recur for right subtree: Call
serializeHelper(root.right = 6, sb).
- Recur for right subtree: Call
-
Processing Node 6:
- Append "6," to
sb→sb = "4,2,1,#,#,3,#,#,6,". - Recur for left child: Node is
null, append "#," →sb = "4,2,1,#,#,3,#,#,6,#,". - Recur for right subtree: Call
serializeHelper(root.right = 7, sb).
- Append "6," to
-
Processing Node 7:
- Append "7," to
sb→sb = "4,2,1,#,#,3,#,#,6,#,7,". - Recur for left child: Node is
null, append "#," →sb = "4,2,1,#,#,3,#,#,6,#,7,#,". - Recur for right child: Node is
null, append "#," →sb = "4,2,1,#,#,3,#,#,6,#,7,#,#,".
- Append "7," to
-
Final Serialized String:
Serialized = "4,2,1,#,#,3,#,#,6,#,7,#,#".
Deserialization Walkthrough:
-
Initialize Queue from Serialized String:
- Split serialized string
"4,2,1,#,#,3,#,#,6,#,7,#,#"into a queue:
Queue = ["4", "2", "1", "#", "#", "3", "#", "#", "6", "#", "7", "#", "#"].
- Split serialized string
-
Start Deserialization:
- Call
deserializeHelper(Queue).
- Call
-
Processing Node 4:
- Dequeue "4" → Create
TreeNode(4). - Recur for left child: Call
deserializeHelper(Queue).
- Dequeue "4" → Create
-
Processing Node 2:
- Dequeue "2" → Create
TreeNode(2). - Recur for left child: Call
deserializeHelper(Queue).
- Dequeue "2" → Create
-
Processing Node 1:
- Dequeue "1" → Create
TreeNode(1). - Recur for left child: Dequeue "#", return
null. - Recur for right child: Dequeue "#", return
null. - Return to Node 2.
- Dequeue "1" → Create
-
Back to Node 2:
- Recur for right child: Call
deserializeHelper(Queue).
- Recur for right child: Call
-
Processing Node 3:
- Dequeue "3" → Create
TreeNode(3). - Recur for left child: Dequeue "#", return
null. - Recur for right child: Dequeue "#", return
null. - Return to Node 4.
- Dequeue "3" → Create
-
Back to Node 4:
- Recur for right child: Call
deserializeHelper(Queue).
- Recur for right child: Call
-
Processing Node 6:
- Dequeue "6" → Create
TreeNode(6). - Recur for left child: Dequeue "#", return
null. - Recur for right child: Call
deserializeHelper(Queue).
- Dequeue "6" → Create
-
Processing Node 7:
- Dequeue "7" → Create
TreeNode(7). - Recur for left child: Dequeue "#", return
null. - Recur for right child: Dequeue "#", return
null.
- Dequeue "7" → Create
-
Final Tree Structure Reconstructed:
- The tree is reconstructed as
[4, 2, 6, 1, 3, null, 7].
- The tree is reconstructed as
Code
Complexity Analysis
TIme Complexity
- Serialization Complexity:
- Time Complexity: The
serializemethod uses a pre-order traversal to visit each node exactly once, resulting in a time complexity of, where nis the number of nodes in the BST.
- Time Complexity: The
- Deserialization Complexity:
- Time Complexity: The
deserializemethod rebuilds the tree by processing each node value from the serialized string. This takestime since each node is processed once.
- Time Complexity: The
Space Complexity
- Serialization Complexity:
- Space Complexity: The space complexity is
due to the queue used to store the node values during reconstruction.
- Space Complexity: The space complexity is
- Deserialization Complexity:
- Space Complexity: The space complexity is also
because we store the serialized result in a string and also use a StringBuilderto construct it.
- Space Complexity: The space complexity is also
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
TIme Complexity
Space Complexity